﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BacktrackingCode
{
    //子集
    class SubSetCode
    {
        //=========================================力扣78 子集
        //给定一组不含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）
        //解集不能包含重复元素
        List<IList<int>> result;
        List<int> path;
        public IList<IList<int>> Subsets(int[] nums)
        {
            result = new List<IList<int>>();
            path = new List<int>();
            BackTracking(nums, 0);
            return result;
        }
        void BackTracking(int[] nums, int startIndex)
        {
            result.Add(new List<int>(path));// 收集子集，要放在终止添加的上面，否则会漏掉自己
            if (startIndex > nums.Length)
            {
                return;
            }

            for (int i = startIndex; i < nums.Length; i++)
            {
                path.Add(nums[i]);// 子集收集元素
                BackTracking(nums, i + 1);// 注意从i+1开始，元素不重复取
                path.RemoveAt(path.Count - 1);// 回溯
            }
        }

        //=====================================力扣90 子集2
        //给定一个整数数组nums，其中可能包含重复元素，请你返回该数组所有可能的子集
        //解集不能包含重复子集，返回的解集中，子集可以按任意顺序排列
        public IList<IList<int>> SubsetsWithDup(int[] nums)
        {
            result = new List<IList<int>>();
            path = new List<int>();
            Array.Sort(nums);// 去重需要排序
            BackTracking_2(nums, 0);
            return result;
        }
        void BackTracking_2(int[] nums, int startIndex)
        {
            result.Add(new List<int>(path));
            if(startIndex > nums.Length)
            {
                return;
            }

            for(int i = startIndex; i<nums.Length;i++)
            {
                // 而我们要对同一树层使用过的元素进行跳过
                if (i > startIndex && nums[i] == nums[i - 1])// 注意这里使用i > startIndex
                    continue;

                path.Add(nums[i]);
                BackTracking_2(nums, i + 1);
                path.RemoveAt(path.Count - 1);
            }
        }

        //================================================力扣491 递增子序列
        //给你一个整数数组nums,找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案
        //数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况
        //-100 <= nums[i] <= 100,1 <= nums.length <= 15
        public IList<IList<int>> FindSubsequences(int[] nums)
        {
            result = new List<IList<int>>();
            path = new List<int>();
            BackTracking_3(nums, 0);
            return result;
        }
        void BackTracking_3(int[] nums, int startIndex)
        {
            if (path.Count > 1)//递增子序列大小至少为2
                result.Add(new List<int>(path));

            if(startIndex > nums.Length)
            {
                return;
            }

            //可以使用set来去重，但小范围时，用数组更快
            int[] used = new int[201];// 这里使用数组来进行去重操作，题目说数值范围[-100, 100]
            for (int i = startIndex;i<nums.Length;i++)
            {
                if ((path.Count > 0 && nums[i] < path.Last())
                    || used[nums[i] + 100] == 1)
                    continue;

                used[nums[i] + 100] = 1;//记录这个元素在本层用过了，本层后面不能再用了
                path.Add(nums[i]);
                BackTracking_3(nums, i + 1);
                path.RemoveAt(path.Count - 1);
            }

        }












    }
}
